package SegmentTree;

public class SegmentTree {


    private static final int MAXN = 10;
    private static long[] arr = new long[MAXN];
    private static long[] sum = new long[MAXN << 2];
    private static long[] add = new long[MAXN << 2];

    public static void build(int l, int r, int i) {
        // base case: 范围内只有一个数
        if (l == r) {
            sum[i] = arr[i];
        } else {
            // l < r
            int mid = (l + r) >> 1;
            build(l, mid, i << 1);
            build(mid + 1, r, i << 1 | 1);
            up(i);
        }
    }

    /**
     * @param jobl 任务的左边界
     * @param jobr 任务的右边界
     * @param jobv 任何的修改值
     * @param l    当前的左边界
     * @param r    当前的右边界
     * @param i    范围内元素的信息记录的位置
     */
    public static void add(int jobl, int jobr, int jobv, int l, int r, int i) {
        // base case: 当前的范围集合是任务集合的子集
        if (jobl <= l && r <= jobr) {
            lazy(i, jobv, r - l + 1);
        } else {
            int mid = (l + r) >> 1;
            // 下发一层懒信息
            down(i, mid - l + 1, r - mid);

            if (jobl <= mid) {
                add(jobl, jobr, jobv, l, mid, i << 1);
            }
            if (jobr > mid) {
                add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);
            }
            // 根据子节点更新的信息，重新计算父节点的值
            up(i);
        }
    }

    /**
     * @param jobl 任务的左边界
     * @param jobr 任务的右边界
     * @param l    当前的左边界
     * @param r    当前的右边界
     * @param i    范围内元素的信息记录的位置
     * @return 任务范围内数的和 == 集合[jobl...jobr]和集合[l...r]的交集的元素和
     */
    public static long query(int jobl, int jobr, int l, int r, int i) {
        // base case
        if (jobl <= l && r <= jobr) {
            // 当前的范围完全在任务范围内，直接返回范围值
            return sum[i];
        }
        // 当前的范围不完全在任务范围内，需要到左右子树去查找更小的范围
        int mid = (l + r) >> 1;
        down(i, mid - l + 1, r - mid);

        long ans = 0;
        // 左侧是否有任务范围值
        if (jobl <= mid) {
            ans += query(jobl, jobr, l, mid, i << 1);
        }
        // 右侧是否有任务范围值
        if (jobr > mid) {
            ans += query(jobl, jobr, l, mid + 1, i << 1 | 1);
        }
        return ans;
    }

    /**
     * 当前范围不能被任务范围全包，把该范围上积攒的懒信息往下发一层
     * 本方法就是下发过程
     *
     * @param i  当前范围的信息记录下标
     * @param ln 左子树的节点数目
     * @param rn 右子树的节点数目
     */
    private static void down(int i, int ln, int rn) {
        // 判断是否有懒信息
        if (add[i] != 0) {
            // 左子树下发懒信息
            lazy(i << 1, add[i], ln);
            // 右子树下发懒信息
            lazy(i << 1 | 1, add[i], rn);
            // 下发后清空当前节点的懒信息
            add[i] = 0;
        }
    }

    /**
     * @param i 父节点和的值的存储位置
     */
    public static void up(int i) {
        // 父节点的值 = 左子树节点的和 + 右子树节点的和
        sum[i] = sum[i << 1] + sum[i << 1 | 1];
    }

    /**
     * @param i 当前范围的信息的下标
     * @param v 父节点记录的懒信息
     * @param n 子树的节点数目
     */
    public static void lazy(int i, long v, int n) {
        // 计算当前范围的和
        sum[i] += v * n;
        // 计算当前范围元素的新操作数
        add[i] += v;
    }
}
